package com.zjw.yyyy2021.mmdd0928;

import java.util.HashMap;

/**
 * <p>TODO</p>
 *
 * @author 郑大仙丶
 * @version V1.0.0
 * @date 2021/9/28 21:49
 */
public class MMdd0928 {

    public int pathSum(TreeNode root, int k) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        return preSum(root,k,map,0);
    }

    public int preSum(TreeNode root, int k,HashMap<Integer,Integer> map,int curr){
        if(root == null) return 0;
        int res = 0;
        curr += root.val;

        res = map.getOrDefault(curr - k,0);
        map.put(curr,map.getOrDefault(curr,0) + 1);
        res += preSum(root.left,k,map,curr);
        res += preSum(root.right,k,map,curr);
        map.put(curr,map.getOrDefault(curr,0) - 1);
        return res;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

}
